/**
 * FileName: Beibao1
 * Author:   powersi
 * Date:     2021/2/7 10:19
 * Description: 1
 */
package com.zm.demo.core.leetcode.dynamic;

/**
 * Description: 1
 * Author:      powersi
 * Date:        2021/2/7 10:19
 */
public class Beibao1 {


    public static void main(String[] args) {

        int [] num = {3,4,4,4,5};
        int weight = 11;

//        for (int i = 0; i < num.length; i++) {
            System.out.println(beibao1(num,weight));
            System.out.println(beibao2(num,weight));
//        }

    }


    /**
     * 层层累计，下一层会用上前一个的计算结果
     * 记录计算结果，使用二维 state[n][w], n=物品个数，w=背包最大容量+1
     * 首先第一个满足
     * 每一个物品放入与不放入有两个状态(两条路径)
     *  如果不放入，保持与上一个一致
     *  如果放入，首先判断是否小于等于所需最大值，如果满足，则将其放入，否则不放入，标记为二维数组当前物品个数n，以及累计总量w,即state[n][w] = true
     * @param num
     * @param weight
     * @param n
     * @return
     */
    public static int beibao(int [] num,int weight, int n){
        boolean [][] states = new boolean[num.length][weight+1];
        states[0][0] = true;
        if (num[0] < weight){
            states[0][num[0]] = true;
        }
        for (int i = 1; i < num.length; i++) {
            for (int j = 0; j <= weight; j++) {//不放入第i个的情况，即保持当前列和上一行的列值一致
                if (states[i-1][j] == true){
                    states[i][j] = true;
                }
            }
            for (int j = 0; j <= weight-num[i]; j++) {//放入第i个的值
                if (states[i-1][j] == true){
                    states[i][j+num[i]] = true;
                }
            }
        }
        for (int i = 0; i < states.length ; i++) {
            for (int j = 0; j < states[i].length; j++) {

                System.out.print(states[i][j] ? "1 " : "0 " );
            }
            System.out.println();
        }
        for (int i = weight; i >= 0 ; i--) {
            if (states[num.length-1][i] == true){
                return i;
            }
        }

        return 0;

    }


    public static int beibao1(int[]product, int weight){

        //初始化状态数组
        int[][] state = new int[product.length][weight+1];
        state[0][0] = 1;
        if (product[0] <= weight){
            state[0][product[0]] = 1;
        }

        for (int i = 1; i < product.length; i++) {
            for (int j = 0; j < state[i].length ; j++) {
                if (state[i-1][j] == 1){
                    state[i][j] = 1;
                }
            }

            for (int j = 0; j + product[i] <= weight ; j++) {
                if (state[i-1][j] == 1){
                    state[i][j+product[i]] = 1;
                }
            }
        }

        for (int i = 0; i < state.length ; i++) {
            for (int j = 0; j < state[i].length ; j++) {
                System.out.print(state[i][j] + " ");
            }
            System.out.println();
        }

        for (int i = state[product.length-1].length-1; i >=0  ; i--) {
            if (state[product.length-1][i] == 1){
                return i;
            }
        }

        return 0;
    }

    public static int beibao2(int[]product, int weight){

        //初始化状态数组
        int[] state = new int[weight+1];
        state[0] = 1;
        if (product[0] <= weight){
            state[product[0]] = 1;
        }

        for (int i = 1; i < product.length; i++) {
            for (int j = weight-product[i]; j >=0 ; j--) {
                if (state[i] == 1){
                    state[j+product[i]] = 1;
                }
            }
        }

        for (int j = 0; j < state.length ; j++) {
            System.out.print(state[j] + " ");
        }
        System.out.println();

        for (int i = state.length-1; i >=0  ; i--) {
            if (state[i] == 1){
                return i;
            }
        }

        return 0;
    }
}
